package com.yaoli.ajob;

/**
 * important
 *
 * 动态规划 dp
 *
 * 思路 使用一个数组保存 ，保存前一个数的最大连续和
 *
 * 初始步骤，第一个最大值是第一个数
 *
 * 核心：
 *
 * 对于i，如果 dp[i - 1] 是小于0的数字，说明 不用再使用 dp[i-1] 的值，而使用当前nums[i]的值。
 *
 * Created by will on 2017/4/21.
 */
public class _053_MaximumSubarray {
    public static void main(String[] args) {
        _053_MaximumSubarray maximumSubarray = new _053_MaximumSubarray();

//        int [] nums = {-1,2,1};
        int [] nums = {-2,1,-3,4,-1,2,1,-5,4};
        maximumSubarray.calc(nums);
    }
    public void calc(int nums[]){
        int dp [] = new int[nums.length];

        dp[0] = nums[0];


        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i - 1] > 0){
                dp[i] = dp[i - 1] + nums[i];
            }else{
                dp[i] = nums[i];
            }

            max = Math.max(dp[i],max);
        }


        for(int i = 0 ; i < dp.length ; i++){

        }
        System.out.println(max);
    }


    public int maxSubArray(int[] nums) {

        int table [] = new int[nums.length];
        table[0]=nums[0];
        for(int i=1;i<table.length;i++){
            if(table[i-1]>0){
                table[i]=table[i-1]+nums[i];
            }else{
                table[i]=nums[i];
            }
        }
        int max=Integer.MIN_VALUE;
        for(int i=0;i<table.length;i++){
            max=Math.max(table[i],max);
        }
        System.out.println(max);
        return max;
    }

}
